import java.util.PriorityQueue;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/11 8:28
 * @description:
 */
public class Solution295 {
    public static class MedianFinder {
        PriorityQueue<Integer> small;//大顶堆但是里面的元素较小
        PriorityQueue<Integer> large;//小顶堆但是里面的元素较大

        public MedianFinder() {
            large = new PriorityQueue<>();
            small = new PriorityQueue<>((x1, x2) -> x2 - x1);
        }

        public void addNum(int num) {
            if (small.size() == 0 || num < small.peek()) {
                small.offer(num);
            } else {
                large.offer(num);
            }
            if (Math.abs(small.size() - large.size()) > 1) {
                if (small.size() < large.size()) {
                    small.offer(large.poll());
                } else {
                    large.offer(small.poll());
                }
            }
        }

        public double findMedian() {
            if (large.size() < small.size()) {
                return small.peek();
            } else if (large.size() > small.size()) {
                return large.peek();
            } else {
                return (small.peek() + large.peek()) / 2.0;
            }
        }
    }

    public static void main(String[] args) {
        Solution295.MedianFinder medianFinder = new Solution295.MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }
}
